1. Field of the Invention
The present invention relates digital printing devices and computer systems that utilize such devices, and in particular to techniques for reducing errors in tonal rendition produced by such devices.
2. Description of the Related Art
Most computer-driven printing devices, such as laser, dot-matrix and ink-jet printers, print in a binary fashion: the output medium is divided into an array of picture elements, or "pixels," and the devices can either print a small colored dot at each pixel location or leave the location blank. In the case of monochrome printers, all of the dots are printed in a single color, whereas color printers select a dot color from a small set of colors.
Pictorial imagery, by contrast, is continuous in tonality, exhibiting a "gray scale" that extends over a large range of tonal levels. If such a "continuous-tone" image is divided into pixels, each will exhibit a gray-scale tone. In order to reproduce the image by means of an electronic printing device capable of applying only a single-toned dot, these gray-scale tones must be converted into a binary format. The conversion process, which may take many forms, is generically referred to as "halftoning." Although a halftone image consists solely of a spatial arrangement of binary colored or uncolored dots, the human visual system integrates this pattern to create an illusion of a continuous-tone original.
During the printing process, the image to be printed is divided into a series of pixels, and the tonal value of the image at each pixel is quantized as a multibit digital word. The pixels are provided as a stream of digital words to the printer, which processes, or halftones the words into a "raster" of binary values. Numerous electronic halftoning algorithms have been developed and refined over the years. In their simplest form, such algorithms compare an input intensity level with a threshold level, and generate a binary output pixel value depending the relative values.
For example, a digital scanner processing a continuous-tone image might represent detected light intensities as multibit signals; the numerical value of these signals frequently ranges from 0 to 255, corresponding to a 256-level gray scale. The halftoning process compares the scanner output signals with a periodically repeated array of threshold "screen" values to produce the requisite binary pixels. In such a system, the 8-bit input signals have effectively been compressed into a grid of single-valued elements.
Naturally, such compression implies significant loss of information. Additional techniques have therefore been developed to reduce the visual distortions created by the halftoning process. One approach, known as error diffusion, distributes the "quantization error" (i.e., the difference between the input tonal value represented by a multibit word and the output value represented by a single bit) proportionally among neighboring pixels. Quantization error occurs wherever the original image contains gray values; in an 8-bit gray scale, for example, such error is absent only at signal levels of 0 or 255.
In general, error diffusion produces an excellent image reproduction, but also creates well-known artifacts called "worms" and "snowplowing" which degrade image quality. Various attempts have been made to reduce artifact patterns; these have generally been only partially successful, as the patterns are not totally removed, but instead are changed in appearance or orientation in a manner that is more pleasing to the eye.
Another problem inherent in the error-diffusion method is the large number of computations necessary to process an image. Since several computations, including multiplications, must be performed on each processed pixel, millions of computations may be necessary to generate the final output values for a typical high-resolution image. In addition, it is necessary to store at least one line of error values that are to be applied to the succeeding line of image values. This large number of computations and the required storage combine to increase the processing time for each image, resulting in decreased printer throughput.
As a result, alternatives to error diffusion have been developed to reduce the number of computations necessary to process an image. One such alternative is called "ordered dithering," in which an array of predetermined (and generally different) threshold values--a "dither array"--with the same spacing as the image pixels is conceptually overlaid onto the image pixel array. If the dither array is smaller than the image array, then the dither array is repeated side-by-side or "tiled" over the image array to produce a repetitive pattern. Each pixel thus has two values conceptually associated with it, namely, the actual pixel tonal value and the threshold value of the overlaid dither array cell to which it is compared. Equivalently, the values in the dither array can be added to the tonal value of each pixel, and the augmented value compared with a fixed threshold. In either case, an output value is generated based on the comparison. Since the processing of each pixel involves only a simple comparison and is independent of neighboring pixel values, the computation time required to process an entire image is substantially less than that required for error diffusion.
However, the quality of the resulting processed image depends entirely on the threshold values chosen for the dither array. Two types of dither arrays are commonly used. In a "clustered-dot" dither array, the threshold values are organized into small groups having closely spaced values. These clusters mimic "dots" of various sizes, and thus produce processed images visually similar to those produced by the traditional halftone screen used for many years in photoengraving processes.
In "dispersed-dot" dithering, large and small threshold values are spread even throughout the array. This technique enhances the printable gray scale as well as resolution. For image-reproduction devices capable of clearly displaying a single isolated pixel, the dispersed-dot dither array usually produces better image quality than the clustered-dot dither array; this is because dispersed-dot arrays achieve better high-frequency fidelity and create a better illusion of a continuous gray region than do clustered-dot arrays of the same resolution and period.
With both types of arrays, a tradeoff generally exists between the number of discrete gray levels that can be represented (which increases as the number of dither-array elements or cells increases) and the appearance of annoying low-frequency geometric patterns in areas of uniform gray (which also appear as the number of dither-array elements increases). Increasing the size of the dither array also tends to decrease image resolution as low-frequency values disappear. One way to reduce these patterns while retaining resolution is to make the size of the dither array very large and utilize homogeneous patterns of threshold values, where successive threshold values "turn on" pixels in a homogeneous, random pattern. However, as the array size increase, assigning threshold values to the array cells to produce the necessary pattern becomes a nontrivial matter. Accordingly, various schemes have been developed to derive random value sequences and assign them to the array cells.
All digital halftoning techniques assume perfectly square pixels, which fully cover the printable area of the recording medium. If this were truly the case, the printer output density would be directly proportional to the input (scanned) density of the original; the ideal case, as indicated by the 45.degree. line in FIG. 1, occurs when output density precisely matches input density. In fact, however, the response of real electronic printing devices is typically nonlinear because such devices do not generate perfectly adjacent, nonoverlapping square dots; instead, they tend to produce dots that are more round than square, and which extend beyond the square boundaries of ideal pixels. This is necessary to ensure that adjacent dots fully overlap without leaving uncolored space (so that, for example, fully colored fields are printed solidly, without uncolored gaps) under a variety of printing conditions. Because the dots are larger than what is assumed in the halftoning algorithm, a plot of printer output density (expressed in terms of normalized percentage dot area) as a function of input gray-scale density--with larger values along the axes corresponding to lower density values, so that the maximum density occurs at the origin--ordinarily follows a curve similar to f(x) in FIG. 1; the printed image, accordingly, appears darker than it should. The precise form of f(x) is determined both by characteristics of the printer and the selected halftoning algorithm.
To compensate for this effect, the function f(x) is defined mathematically through piecewise density measurements and regression, and an inverse (transfer) function, f.sup.-1 (x), defined as well. The latter function, when applied to incoming source data, offsets the effects of the printer function, correcting the data so that processing by the halftoning algorithm will produce a printed output whose density characteristics more closely match that of the original.
Although this technique, known as "predistortion," produces printed output superior to unmodified halftoned image data, correction to the ideal linear response does not necessarily produce the most visually desirable printed copy. This is due to the complex interactions between the human visual system and the patterns produced by halftoning algorithms on a variety of scales. Subjective responses frequently vary with both the halftoning algorithm employed and the degree of predistortion. See, e.g., Trontelj et al., "Optimal Halftoning Algorithm Depends on Printing Resolution," SID 92 Digest at 749 (1992). The present invention is directed toward improving predistortion to enhance the visual appearance of printed output.